//给定一个正整数 n ，你可以做如下操作：
//
//
// 如果 n 是偶数，则用 n / 2替换 n 。
// 如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
//
//
// n 变为 1 所需的最小替换次数是多少？
//
//
//
// 示例 1：
//
//
//输入：n = 8
//输出：3
//解释：8 -> 4 -> 2 -> 1
//
//
// 示例 2：
//
//
//输入：n = 7
//输出：4
//解释：7 -> 8 -> 4 -> 2 -> 1
//或 7 -> 6 -> 3 -> 2 -> 1
//
//
// 示例 3：
//
//
//输入：n = 4
//输出：2
//
//
//
//
// 提示：
//
//
// 1 <= n <= 2³¹ - 1
//
// Related Topics 贪心 位运算 记忆化搜索 动态规划 👍 141 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    // S3
    Map<Integer, Integer> memo = new HashMap<Integer, Integer>();

    public int integerReplacement(int n) {
        // S1 my, Memory Limit Exceeded
//        int[] dp = new int[n + 1];
//
//        for (int i = 2; i <= n; i++) {
//            if (i % 2 == 0) {
//                dp[i] = dp[i / 2] + 1;
//            } else {
//                dp[i] = Math.min(dp[i - 1], dp[(i + 1) / 2] + 1) + 1;
//            }
//        }
//        return dp[n];

        // S2 enumerate
//        if (n == 1) {
//            return 0;
//        }
//        if (n % 2 == 0) {
//            return 1 + integerReplacement(n / 2);
//        }
//        return 2 + Math.min(integerReplacement(n / 2), integerReplacement(n / 2 + 1));

        // S3 memory enumerate
//        if (n == 1) {
//            return 0;
//        }
//        if (!memo.containsKey(n)) {
//            if (n % 2 == 0) {
//                memo.put(n, 1 + integerReplacement(n / 2));
//            } else {
//                memo.put(n, 2 + Math.min(integerReplacement(n / 2), integerReplacement(n / 2 + 1)));
//            }
//        }
//        return memo.get(n);

        // S4 greedy
        int ans = 0;
        while (n != 1) {
            if (n % 2 == 0) {
                ++ans;
                n /= 2;
            } else if (n % 4 == 1) {
                ans += 2;
                n /= 2;
            } else {
                if (n == 3) {
                    ans += 2;
                    n = 1;
                } else {
                    ans += 2;
                    n = n / 2 + 1;
                }
            }
        }
        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
